package suanfa;

import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/9/22-下午2:47
 * Since  :   1.0
 * Version:   1.0
 */


public class xiaohongshu {
    public static int findMin(int[] nums) {

        int result = 0;
        if (nums.length == 1) {
            return nums[0];
        }

        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            if (result > 0) {
                result -= nums[i];
            } else {
                result += nums[i];
            }
        }
        return result > 0 ? result : -result;
    }

    public static int[] findTheMcn(ArrayList<ArrayList<String>> nums, int specialValue) {

        if (nums.size() <= 1 || specialValue < 1) {
            return null;
        }


        for (int left = 0; left < nums.size(); left++) {
            HashSet<String> results = new HashSet<>();
            ArrayList<String> first = nums.get(left);
            for (String s : first) {
                results.add(s);
            }
            for (int right = left + 1; right < nums.size(); right++) {
                ArrayList<String> second = nums.get(right);
                for (String s : second) {
                    results.add(s);
                }
                if (results.size() == specialValue) {
                    int[] thefinalResult = {left + 1, right + 1};
                    return thefinalResult;
                }
            }

        }
        return null;
    }



//
//    public static List<List<Integer>> permute(int[] nums) {
//        Boolean[] used=new Boolean[nums.length];
//        Arrays.fill(used,false);
//        backtracking(nums,used,new ArrayList<>());
//        return result;
//    }


    public static List<List<Integer>> permute(int[] nums) {
        Boolean[] booleans = new Boolean[nums.length];
        Arrays.fill(booleans, false);

        List<List<Integer>> result = new ArrayList<>();
        backtracking(nums, booleans, new ArrayList<>(), result);
        return result;
    }

    public static void backtracking(int nums[],Boolean booleans[],List<Integer>list,List<List<Integer>>lists){
        if (list.size()==booleans.length) {
            lists.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            if (booleans[i]) {
                continue;
            }
            booleans[i]=true;
            list.add(nums[i]);
            backtracking(nums,booleans,list,lists);
            list.remove(list.size()-1);
            booleans[i]=false;
        }

    }

//    public static void backtracking(int nums[], Boolean booleans[], List<Integer> list, List<List<Integer>> result) {
//        if (list.size() == nums.length) {
//            result.add(new ArrayList<>(list));
//            return;
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            if (booleans[i]) {
//                continue;
//            }
//            booleans[i] = true;
//            list.add(nums[i]);
//            backtracking(nums, booleans, list, result);
//            list.remove(list.size() - 1);
//            booleans[i] = false;
//
//        }
//
//
//    }


    public static List<List<Integer>> combine(int n, int k) {
        Boolean[] visited = new Boolean[n];
        Arrays.fill(visited, false);
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> lists = new ArrayList<>();
        int start = 0;
        backtracking2(start, visited, list, lists, k);
        return lists;

    }

    private static void backtracking2(int start, Boolean[] visited, List<Integer> list, List<List<Integer>> lists, int end) {
        if (list.size() == end) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int index = start; index < visited.length; index++) {
            if (visited[index]) {
                continue;
            }
            visited[index] = true;
            list.add(index + 1);
            backtracking2(index + 1, visited, list, lists, end);
            list.remove(list.size() - 1);
            visited[index] = false;

        }



    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> lists = new ArrayList<>();
        backtracking3(candidates, target, list, lists,0);
        return lists;
    }

    private static void backtracking3(int[] candidates, int target, List<Integer> list, List<List<Integer>> lists,int start) {
        if (countSum(list) > target) {
            return;
        }
        if (countSum(list) == target) {
            lists.add(new ArrayList<>(list));
        }
        for (int i = start; i < candidates.length; i++) {
            list.add(candidates[i]);
            backtracking3(candidates, target, list, lists,i);
            list.remove(list.size()-1);
        }


    }

    public static int countSum(List<Integer> list) {
        int sum = 0;
        for (int i : list) {
            sum += i;
        }
        return sum;
    }

    public static int  KMP(String s,String subString){
      int left=0;
      int right=0;
      int next[]=findNext(subString);
      while (left<s.length()){


          if (s.charAt(left)==subString.charAt(right)){
              left++;
              right++;
          }else {

              right=next[right];
              if (right==0){
                  left++;
              }
          }
          if (right==subString.length()){
              return left-right;
          }


      }
      return -1;
    }

    public static int[]  findNext(String subString){
        int next[]=new int[subString.length()];
        next[0]=0;
        next[1]=0;
        for (int i = 2; i <subString.length() ; i++) {
            String s=subString.substring(0,i);
            int left=0;
            int right=s.length()-1;
            int count=0;
            while (left<right){
                if (s.charAt(left)==s.charAt(right)){

                    count++;

                }else {
                    break;
                }
                left++;
                right--;
            }
            next[i]=count;
        }
        return next;
    }


    public static void main(String[] args) {
//        int []nums={1,2,3,};
////        permute(nums);
//        combine(4,2);
//        int []nums={2,3,6,7};
//        List<List<Integer>> lists = combinationSum(nums, 7);
//        for (List<Integer> list:lists){
//            for (int i:list){
//                System.out.print(i);
//            }
//            System.out.println();
//        }
//        combine(4,2);
        String myString = "aabaabaag";
        String s = "aabaaf";
//        0010120
        int[] next = findNext(s);
        int kmp = KMP(myString, s);
        System.out.println(kmp);

    }

}
